package com.gitee.ed.arithmetic.leetcode.answer.answer_1_100.answer_1_10;

import com.gitee.ed.arithmetic.leetcode.solution.solution_1_100.solution_1_10.Solution10;

/**
 * @author hongda.li
 */
public class Answer10 implements Solution10 {

    @Override
    public boolean isMatch(String s, String p) {
        char[] str = s.toCharArray();
        char[] pattern = p.toCharArray();
        return isMatchChar(str, 0, pattern, 0);
    }

    private boolean isMatchChar(char[] str,
                                int startOfStr,
                                char[] pattern,
                                int startOfPattern) {
        if (startOfPattern >= pattern.length) {
            return startOfStr >= str.length;
        }

        boolean match = startOfStr < str.length
                // 匹配字符和待匹配字符相等或匹配字符为通配符
                && ((str[startOfStr] == pattern[startOfPattern]) || pattern[startOfPattern] == '.');

        if (pattern.length - startOfPattern >= 2 && pattern[startOfPattern + 1] == '*') {
            return isMatchChar(str, startOfStr, pattern, startOfPattern + 2)
                    || (match && isMatchChar(str, startOfStr + 1, pattern, startOfPattern));
        }

        return match && isMatchChar(str, startOfStr + 1, pattern, startOfPattern + 1);
    }
}
